﻿//Write a program that finds the sequence of maximal sum in given array. 
//Example: {2, 3, -6, -1, 2, -1, 6, 4, -8, 8} -> {2, -1, 6, 4}


using System;

public class SequenceOfMaximalSum
{
    public static void Main()
    {
        Console.Write("Enter the number of elements of the array: ");
        int elementsCount = int.Parse(Console.ReadLine());        
        Console.WriteLine("Enter {0} elements of the array", elementsCount);
        int[] array = new int[elementsCount];
        for (int i = 0; i < elementsCount; i++)
        {
            array[i] = int.Parse(Console.ReadLine());
        }
             
        int maximalSum = array[0];
        int tempSum = array[0];        
        int begin = 0;
        int beginTemp = 0;
        int end = 0;

        for (int i = 1; i < array.Length; i++)
        {            
            if (tempSum < 0)
            {
                tempSum = array[i];
                beginTemp = i;
            }
            else
            {
                tempSum += array[i];                
            }
                        
            if (tempSum > maximalSum)
            {
                maximalSum = tempSum;
                begin = beginTemp;
                end = i;
            }
        }

        Console.Write("Max sum = {0} -> {{", maximalSum);
        for (int i = begin; i <= end; i++)
        {
            if (i < end)
            {
                Console.Write("{0}, ", array[i]);
            }
            else
            {
                Console.Write("{0}", array[i]);
            }
        }

        Console.WriteLine('}');
    }
}